#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s)
    {
        // string ans;
        // string temp;
        // for(int i=0;i<s.length();i++)
        // {
        //     for(int j=i;j<s.length();j++)
        //     {
        //         temp=temp+s[j];
        //         string tem=temp;
        //         reverse(tem.begin(),tem.end());
        //         if(temp==tem)
        //         {
        //             ans=ans.length()>temp.length()?ans:temp;
        //         }
        //     }
        //     temp.clear();
        // }
        // return ans;

        int len = s.size();
        if (len == 0 || len == 1)
        {
            return s;
        }
        int start = 0;
        int max = 1;
        vector<vector<int>>  dp(len, vector<int>(len));
        for (int i = 0; i < len; i++)
        {
            dp[i][i] = 1;
            if (i < len - 1 && s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                max = 2;
                start = i;
            }
        }
        for (int l = 3; l <= len; l++)
        {
            for (int i = 0; i + l - 1 < len; i++)
            {
                int j = l + i - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1] == 1)
                {
                    dp[i][j] = 1;
                    start = i;
                    max = l;
                }
            }
        }
        return s.substr(start, max);

    }
};

int main()
{
    Solution S;
    return 0;
}